# distribution/hw03/modPolynomial.py              David MacQuigg ece373 10/23/07
'''A polynomial is made of one or more monomial elements.

    >>> polyDict = {55: -6.55, 7: 8.7, 1: -2.1, 0: 2./3}
    >>> print Polynomial(polyDict)
    -6.55x^55 + 8.7x^7 - 2.1x + 0.666666666667
'''
## import array  # for more efficient processing of large arrays.       # [1]
import copy  # copy module includes "deepcopy"                          # [2]

from modMonomial  import Monomial
from modCloneable import Cloneable

class Polynomial(Cloneable):
    '''Class to manipulate and display univariate polynomials of the form
(a_N)x^N + ... + (a_1)x + a_0
'''

    def __init__(self, values=None):
        '''Create a Polynomial with the given initial values, which may be
another Polynomial, a Monomial, or a list of Monomials. The default None creates
a Polynomial of a constant 0.
'''
        if values in (None, [], {}, ''):
        # Create a Polynomial with a single constant 0.0 Monomial
            self._elements = {0: Monomial()}
            return
        
        if type(values) == Polynomial:
        # Create a Polynomial from a deep copy of an existing Polynomial
            self._elements = copy.deepcopy(values._elements)
            return
        
        if type(values) == Monomial:
        # Create a polynomial with a single Monomial element
            exp = values.getExponent()     # an int
            mony = copy.deepcopy(values)   # a Monomial
            self._elements = {exp: mony}
            return
        
        if type(values) == list:
            self._elements = {}
            for mony in values:  # iterate over list elements           # [3]
                exponent = mony.getExponent()
                if type(mony) != Monomial:
                    raise TypeError, "list must contain only Monomials"
                if self._elements.has_key(exponent):
                    raise ValueError, "list must not have duplicate exponents"
                self._elements[exponent] = copy.deepcopy(mony)
            return

        if type(values) == dict:
            '''Unrequired feature.  This one is handy for testing.  Less work
            than building all the Monomials first.
            '''
            self._elements = {}
            for exp in values:  # iterate over keys from dict           # [3]
                coeff = values[exp]
                assert type(exp) == int
                assert type(coeff) in (float, int)
                self._elements[exp] = Monomial(exp, coeff)
            return

        raise TypeError, ("Polynomial can be built only from another " +
                           "Polynomial, a Monomial, or a list of Monomials.")

    def setCoefficientByExponent(self, exponent, coefficient):
        '''Set the specified element in the Polynomial to have the specified
        coefficient.  Remove any elements that would be zero.'''
        if coefficient != 0.0:
            self._elements[exponent] = Monomial(exponent, coefficient)
        else:
            if self._elements.has_key(exponent):
                del self._elements[exponent]  # remove this element

    def getCoefficientByExponent(self, exponent):
        '''Get the coefficient of a particular exponent in the Polynomial.
        >>> poly5.getCoefficientByExponent(55)
        1.7
        >>> poly5.getCoefficientByExponent(56)
        0.0
        '''
        if self._elements.has_key(exponent):
            return self._elements[exponent].getCoefficient()
        else:
            return 0.0  # no element with this exponent

    def __str__(self):
        '''Return a string representation in the form:
        (a_N)x^N + ... + (a_1)x + a_0
        
        >>> polyDict = {55: -6.55, 7: 8.7, 1: -2.1, 0: 2./3}
        >>> print Polynomial(polyDict)
        -6.55x^55 + 8.7x^7 - 2.1x + 0.666666666667
        >>> print Polynomial({})
        0.0
        '''
        polydict = self._elements  # dict of all elements
        if polydict == {}:  # an empty polynomial
            return '0.0'
        keys = self._getSortedExponents() # highest first [55, 7, 1, 0]
        kmax = keys[0]
        polyString = ''
        for k in keys:
            exponent = k; sign = '+'
            assert type(exponent) == int  # check for bad data
            assert exponent >= 0
            coefficient = polydict[k].getCoefficient()
            if coefficient < 0:
                sign = '-'; coefficient = -coefficient
            if exponent > 1:  xterm = 'x^%s' % exponent
            if exponent == 1: xterm = 'x'
            if exponent == 0: xterm = ''
                
            if k == kmax:    # special handling of first term
                if sign == '-':
                    polyString += '-'  # leading '-'
                polyString += '%s%s' % (coefficient, xterm)
            else:            # all other terms
                polyString += ' %s %s%s' % (sign, coefficient, xterm)

        return polyString

    def clone(self):
        return Polynomial(self)  # a deep copy of self

###  Private methods =======================================

    def _getSortedExponents(self):                                      # [4]
        '''Retrieve a sorted list of the Polynomial exponents.
        >>> poly5._getSortedExponents()
        [55, 3, 0]
        '''
        exponentsList = self._elements.keys()
##        exponentsList.sort(reverse=True)  # reverse order (highest first)
        exponentsList.sort()     # These two statements are needed for backward
        exponentsList.reverse()  # compatiblity. reverse=True was added in 2.4
        return exponentsList

    def _deepCopyElements(self):                                        # [4]
        '''Performs a deep copy of the Monomial elements of a Polynomial.

        >>> poly = poly3c._deepCopyElements()
        >>> print poly
        8.8x^8 + 7.7x^7
        '''
        poly = Polynomial()  # a new Polynomial with only a zero element
        del poly._elements[0]
        for exp, mony in self._elements.items():  # iterate over (key, value)
            poly._elements[exp] = copy.deepcopy(mony)
        return poly


if __name__ == '__main__':

    # sample data for testing
    poly0 = Polynomial()
    mony1 = Monomial(7, 7.7)
    poly1 = Polynomial(mony1)
    mony2 = Monomial(8, 8.8)
    monyList = [mony1, mony2]
    poly3 = Polynomial(monyList)
    poly3c = Polynomial(poly3)  # a clone of poly3
    
    polyDict5 = {55: 1.7, 3: -2.1, 0: 4.2}
    poly5 = Polynomial(polyDict5)
    polyDict6 = {55: 0.3, 4: 1.2, 0: -3.1}
    poly6 = Polynomial(polyDict6)
    
    def unittests():
        '''
    >>> poly5.setCoefficientByExponent(7,7.7)
    >>> print poly5
    1.7x^55 + 7.7x^7 - 2.1x^3 + 4.2
    >>> poly5.setCoefficientByExponent(7,0.0)
    >>> print poly5
    1.7x^55 - 2.1x^3 + 4.2
    >>> poly5.setCoefficientByExponent(7,7.7)
    >>> print poly5
    1.7x^55 + 7.7x^7 - 2.1x^3 + 4.2
    >>> poly5.setCoefficientByExponent(7,8.8)
    >>> print poly5
    1.7x^55 + 8.8x^7 - 2.1x^3 + 4.2

    >>> poly7 = Polynomial()          # null polynomial
    >>> poly7.__str__()
    '0.0'
    >>> poly8 = Polynomial({55: 0.3, 4: 1.2})    # no x^0 term
    >>> print poly8
    0.3x^55 + 1.2x^4
        '''
    from doctest import testmod
    testmod(verbose=True)
    
''' Notes
[1] We have chosen to store the elements of our polynomial in a Python dict
structure, using as keys the integer exponents of each term in the polynomial.
Python's builtin dict, or dictionary, is similar to a Java HashMap.  It allows:
- compact storage of sparse structures, e.g. a polynomial with only a few terms
having large exponents.
- fast access to specified elements, e.g. creating or adding to a specific term
- slow but acceptable performance in generating a sorted list, e.g. as needed
for a canonical representation of the polynomial.

For polynomials with a really large number of elements, we might change the dict
to one of the array structures available in Python's standard library.  See
"Array Processing", Ch.16 in Martelli's Python Nutshell, 2nd ed.

[2] deepcopy() works with any Python object.

[3] Python iterators are cool!  For simple objects like lists and dicts,
everything is done for us.  Rarely do we need to write our own __iter__ method.
List iterators return the list items.  Dict iterators return the keys to the
dict.  We don't need loop index variables, termination conditions, or any other
clutter found in traditional languages.

[4] Methods _getSortedExponents and _deepCopyElements are provided only to
follow the form of the assignment in Java.  Python's sort function is simple
enough that this would normally be done inline.  Python's deepcopy function
copies all the way to the bottom, so there is no need to handle each element
separately. All we really need is return Polynomial(self).
'''
